1. Field
The present invention relates to circuit design, and, more particularly, to systems and techniques for processing and storing information regarding circuit elements.
2. Description of the Related Art
Geometry databases (GDBs) are often used to support circuit design. A geometry database provides geometrical relationship information regarding elements of a design area to various functional modules of an automated design system. For example, during the physical design phase in a typical Very Large Scale Integration (VLSI) circuit design environment, such functional modules often need to access a geometry database to support inquiries about the geometrical relationships between rectangular tiles. For example, a detail router accesses a geometry database for track clearance queries. Other modules access geometry databases for other purposes.
One fundamental query that a geometry database typically supports is the area query. An area query finds a list of tiles which a rectangular area overlaps. Some other useful queries can be answered based on the area query. For instance, in a point search, the query finds a list of covering tiles for a given point. Because a point is a degenerate rectangle, this query can be answered by an area search. Similarly, in a line search, the query finds a list of overlapping tiles for a given line segment on a routing track, which can also be answered by an area search.
A geometry database may take many forms and may be constructed using many methods. One type of geometry database is called shape-based because the geometry database stores tiles directly using a data structure. One brute-force implementation of a shape-based geometry database is to use a linked-list. However, a linked-list is far from being efficient when performing queries. Other types of geometry databases may use random insertion techniques which force dynamic database restructuring and may result in overlapping bounding boxes in different branches, thereby adversely affecting search queries, for example.
Shaped-based GDBs have advantages over other GDB's such as track-based GDBs. Shape-based GDBs are compact because they do not fracture tiles and thus are memory efficient. For the same reason, they keep the integrity of each tile. Tile integrity is a useful feature for a wide range of application tools. For example, in detailed routing, wires may be ripped up. In this case, shape-based geometry databases can be easily maintained, whereas track-based geometry databases cannot. One type of shape-based geometry database uses slit-trees. In such a GDB, chip design area is partitioned into slits along a preferred routing direction. Tiles are inserted into a slit if they overlap with the slit. However, if a tile is running in a non-preferred routing direction then it will be inserted into multiple slits. This will result in a less memory efficient database.
An efficiently built geometry database aids efficiency and speed when handling queries during various design stages. Since the number of calculations performed during circuit design is ever increasing, the industry is always looking for improved techniques for building and using geometry databases, among other improvements.